import java.util.HashMap;
import java.util.Map;

/**
 * 2661. 找出叠涂元素
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。
 * <p>
 * 从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。
 * <p>
 * 请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i 。
 */
public class T2661 {
    public T2661(int[] arr, int[][] mat) {
        /* 超时
        // 记录每行每列的状态；status[i][0] i行，status[i][1]i列
        int[][] status = new int[mat.length*mat[0].length][2];
        for (int i = 0; i < arr.length; i++) {
            boolean find = false;
            for (int j = 0; j < mat.length; j++) {
                if (find){
                    break;
                }
                for (int k = 0; k < mat[0].length; k++) {
                    if (find){
                        break;
                    }
                    if (arr[i] == mat[j][k]){
                        status[j][0]++;
                        status[k][1]++;
                        if (status[j][0] == mat[0].length ||  status[k][1]==mat.length){
                            System.out.println(i);
                            break;
                        }
                        find = true;
                    }
                }
            }
        }*/
        // 记录每行每列的状态；status[i][0] i行，status[i][1]i列
        int[][] status = new int[mat.length * mat[0].length][2];

        int n = mat.length;
        int m = mat[0].length;
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                map.put(mat[i][j], new int[]{i, j});
            }
        }


        for (int i = 0; i < arr.length; i++) {

            int[] ints = map.get(arr[i]);


            status[ints[0]][0]++;
            status[ints[1]][1]++;
            if (status[ints[0]][0] == mat[0].length || status[ints[1]][1] == mat.length) {
                System.out.println(i);
                break;
            }
        }
    }
}
